Dynamic Programming 1

동적 프로그래밍(Dynamic Programming)
1. 최적해의 구조의 특징을 찾는다.
2. 최적해의 값을 재귀적으로 정의한다.
3. 최적해의 값을 일반적으로 상향식(bottom-up) 방법으로 계산한다.
4. 계산된 정보들로부터 최적해를 구성한다.
Cut Rod(막대 자르기)
rn=max(pn,r1+rn−1,r2+rn−2,...,rn−1+r1)
- 하향식 재귀(동적 프로그래밍 X)
T(n)=2^n 의 시간 복잡도를 가짐
#include <iostream>
#include <climits>
int CutRod(int* p, int n){
if(n==0) return 0;
int q=INT_MIN;
for(int i=1; i<=n; ++i){
q=std::max(q, p[i-1]+CutRod(p, n-i));
}
return q;
}
int main(void){
int p[]={1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
int n=sizeof(p)/sizeof(int);
int result=CutRod(p, n);
std::cout<<result<<std::endl;
return 0;
}
동적 프로그래밍
- 메모하기를 이용한 하향식
하향식 재귀 과정에서 부분 문제의 결과를 배열이나 해시 테이블에 저장
T(n)=\Theta(n^2)
#include <iostream>
#include <climits>
int MemoizedCutRodAux(int* p, int n, int* r){
if(r[n]>=0) return r[n];
int q;
if(n==0) q=0;
else{
q=INT_MIN;
for(int i=1; i<=n; ++i){
q=std::max(q, p[i-1]+MemoizedCutRodAux(p, n-i, r));
}
}
r[n]=q;
return q;
}
int MemoizedCutRod(int* p, int n){
int r[n+1];
for(int i=0; i<n+1; ++i) r[i]=INT_MIN;
return MemoizedCutRodAux(p, n, r);
}
int main(void){
int p[]={1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
int n=sizeof(p)/sizeof(int);
int result=MemoizedCutRod(p, n);
std::cout<<result<<std::endl;
return 0;
}
- 상향식
부분 문제를 “크기”순으로 정렬한 후, 가장 작은 것부터 문제를 풀어 해를 저장한다.
T(n)=\Theta(n^2)
#include <iostream>
int BottomUpCutRod(int* p, int n){
int r[n+1];
r[0]=0;
for(int j=1; j<=n; ++j){
int q=INT_MIN;
for(int i=1; i<=j; ++i){
q=std::max(q, p[i-1]+r[j-i]);
}
r[j]=q;
}
return r[n];
}
int main(void){
int p[]={1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
int n=sizeof(p)/sizeof(int);
int result=BottomUpCutRod(p, n);
std::cout<<result<<std::endl;
return 0;
}
Cut Rod에서 가장 저렴한 비용(최적해의 값)을 리턴할 뿐 아니라,
해당 최적 값에 이르는 선택도 기록하도록 확장할 수 있다.
#include <iostream>
template <typename T>
struct twoPointer{
T *p1, *p2;
twoPointer(T* _p1, T* _p2): p1(_p1), p2(_p2) {}
~twoPointer(){
delete[] p1;
delete[] p2;
}
};
twoPointer<int> ExtendedBottomUpCutRod(int* p, int n){
int* r=new int[n+1];
int* s=new int[n];
r[0]=0;
for(int j=1; j<=n; ++j){
int q=INT_MIN;
for(int i=1; i<=j; ++i){
if(q<p[i-1]+r[j-i]){
q=p[i-1]+r[j-i];
s[j-1]=i;
}
}
r[j]=q;
}
return twoPointer<int>(r, s);
}
void PrintCutRodSolution(int* p, int n){
twoPointer<int> ret=ExtendedBottomUpCutRod(p, n);
while(n>0){
std::cout<<ret.p2[n-1]<<' ';
n=n-ret.p2[n-1];
}
std::cout<<std::endl;
}
int main(void){
int p[]={1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
int n=sizeof(p)/sizeof(int);
PrintCutRodSolution(p, 7);
return 0;
}